#include <iostream>
#include <vector>
#include "ST.h"
#include "TestSortHelper.h"

using namespace std;
template <typename Key,typename Value>
class SeparateChainingHashST:public ST<Key,Value>{
private:
    int N;//键值对总数
    int M;//散列表大小
    SequentialSearchST<Key,Value>* sts;

    int hash(Key key){
        std::hash<Key> hash_int;
        int h =  hash_int(key)&0x7FFFFFFF%M;
        return h;
    }

public:
    SeparateChainingHashST(int M){
        this->M = M;
        this->N = 0;
        sts = new SequentialSearchST<Key,Value>[M];
        for (int i = 0; i < M; ++i) {
            sts[i] = *(new SequentialSearchST<Key,Value>());
        }
    }

    ~SeparateChainingHashST(){
        delete[] sts;
    }

    Value get(Key key){
        return sts[hash(key)].get(key);
    }

    void put(Key key, Value value){
//        SequentialSearchST<Key,Value> st = sts[hash(key)];
//        st.put(key,value);
        cout<<key<<" hash:"<<hash(key)<<endl;
        sts[hash(key)].put(key,value);
        N++;
    }
    void remove(Key key){
        sts[hash(key)].remove(key);
        N--;
    }
    bool contains(Key key){
        sts[hash(key)].contains(key);
    }
    bool isEmpty(){
        return N==0;
    }
    int size(){
        return N;
    }
    Key min(){
        return NULL;
    }
    Key max(){
        return NULL;
    }
    Key floor(Key key){
        return NULL;
    }//小于等于key的最大值
    Key ceiling(Key key){
        return NULL;
    }//大于等于key的最小值
    int rank(Key key){
        return NULL;
    }//小于key的数量
    Key select(int k){
        return NULL;
    }//排名为key的键
    void print(string head){
        for (int i = 0; i < M; ++i) {
            if(!sts[i].isEmpty())
               sts[i].print(head);
        }
    };

};

template <typename Key,typename Value>
class LinearProbingHashST:public ST<Key,Value>{
private:
    int N;//键值对总数
    int M = 16;//散列表大小
    Key* keys;
    Value* values;

    int hash(Key key){
        std::hash<Key> hash_int;
        int h =  hash_int(key)&0x7FFFFFFF%M;
        return h;
    }

    void _resize(int size){
        Key* keys = this->keys;
        Value* values = this->values;

        this->keys = new Key[size];
        this->values = new Value[size];

        for (int i = 0; i < size; ++i) {
            this->keys[i] = NULL;
        }
        for (int j = 0; j < size; ++j) {
            this->values[j] = NULL;
        }
        int oldM = this->M;
        this->M = size;
        this->N = 0;
        for(int i = 0; i< oldM ; i++){
            if(keys[i]!= NULL)
                this->put(keys[i],values[i]);
        }

        delete keys;
        delete values;
    }

public:
    LinearProbingHashST(int cap = 16){
        keys = new Key[cap];
        for (int i = 0; i < cap; ++i) {
            keys[i] = NULL;
        }
        values = new Value[cap];
        for (int j = 0; j < cap; ++j) {
            values[j] = NULL;
        }
        N = 0;
        M = cap;
    }

    ~LinearProbingHashST(){
        delete[] keys;
        delete[] values;
    }

    Value get(Key key){
        for(int i = hash(key);keys[i] != NULL;i = (i+1)%M){
            if(key == keys[i]){
                return values[i];
            }
        }
        return NULL;
    }

    void put(Key key, Value value){
        if(N>=M/2) {
            print("before resize");
            _resize(M * 2);
            print("after resize");
        }

        int i;
        for(i = hash(key);keys[i] != NULL;i = (i+1)%M){
            if(key == keys[i]){
                values[i] = value;
                return ;
            }
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }
    void remove(Key key){
        if(!contains(key))
            return;
        int i = hash(key);
        while(!key == keys[i])//找到键簇中相等的键
            i = (i+1)%M;
        keys[i] = NULL;
        values[i] = NULL;
        i = (i+1)%M;
        while(keys[i] != NULL){//键簇后面的元素统统重新put
            Key keyToRedo = keys[i];
            Value valToRedo = values[i];

            keys[i] = NULL;
            values[i] = NULL;

            N--;
            put(keyToRedo,valToRedo);
            i = (i+1)%M;
        }
        N--;
        if(N>0 && N==M/8)//调整大小，保证数组占有率在 1/8 到 1/2 之间
            _resize(M/2);
    }
    bool contains(Key key){
        for(int i = hash(key);keys[i] != NULL;i = (i+1)%M){
            if(key == keys[i]){
                return true;
            }
        }
        return false;
    }
    bool isEmpty(){
        return N==0;
    }
    int size(){
        return N;
    }
    Key min(){
        return NULL;
    }
    Key max(){
        return NULL;
    }
    Key floor(Key key){
        return NULL;
    }//小于等于key的最大值
    Key ceiling(Key key){
        return NULL;
    }//大于等于key的最小值
    int rank(Key key){
        return NULL;
    }//小于key的数量
    Key select(int k){
        return NULL;
    }//排名为key的键
    void print(string head){
        cout<<head<<":";
        for (int i = 0; i < M; ++i) {
            if(keys[i]!=NULL)
                cout<<keys[i]<<"-"<<values[i]<<" ";
        }
        cout << endl;
    };

};

int main() {
    ST<int,int> *st = new LinearProbingHashST<int,int>();

    int n = 20;
//    int *arr = TestSortHelper::generateRandomArray(n, 1, n);
    int arr[] = {1,2,20,10,4,11,3,6,1,18,7,4,2,19,4,17,5,17,9,5};
    TestSortHelper::printArray(arr, n);
    for (int i = 0; i < n ; ++i) {
        st->put(arr[i],arr[i]);
    }
    st->print("after put: ");
    cout<<"get(Key key) " << arr[10] << ":" <<st->get(arr[10])<<endl;
    st->remove(arr[10]);
    st->print("remove(Key key) ");
//    cout<<"min() " << ":" <<st->min()<<endl;
//    cout<<"max() " << ":" <<st->max()<<endl;
//    cout<<"floor(Key key) " << arr[10] << ":" <<st->floor(arr[10])<<endl;
//    cout<<"ceiling(Key key) " << arr[10] << ":" <<st->ceiling(arr[10])<<endl;
//    cout<<"rank(Key key) " << arr[10] << ":" <<st->rank(arr[10])<<endl;
//    cout<<"select(int rank) " << st->rank(arr[10]) << ":" <<st->select(st->rank(arr[10]))<<endl;
//    cout<<"size() " << ":" <<st->size()<<endl;
//    cout<<"size(Key lo, Key hi) " << 5 << " " << 12 << ":" <<st->size(5,12)<<endl;

    delete arr;
    delete st;
    return 0;
}